package leetcode.solution;

/**
 *
 * 如果用动态规划则将容量作为dp数组的下标
 */
public class z01背包 {

    /*
     * 动态规划算法求解，时间O(NV),空间O(V)
     * V 容量
     */
    public int ZeroOnePackDP(int V,int[] weight,int[] value){
        int N=weight.length;
        int[] dp = new int[V+1];
        //前i件、承重为j的最大热度
        for(int i=1;i<N+1;i++){
            /*
             *根据动态规划“由下而上”的思想可知，要求的第i步的最优解我们只需要根据第i-1步的最优解即
             *可求得，并且现在是一维数组，所以我们需要对f[j]从后往前更新，这里一定要想明白！
             */
            for(int j=V;j>=weight[i-1];j--){
                //weight和value数组下标是从0开始，而dp数组是从1开始
                dp[j]=Math.max(dp[j-weight[i-1]]+value[i-1], dp[j]);
            }
        }
        return dp[V];
    }


    /**
     * 解决背包问题的递归函数
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    当前待选择的物品索引
     * @param capacity 当前背包有效容量
     * @return 最大价值
     */
    private static int solveKS(int[] w, int[] v, int index, int capacity) {
        //基准条件：如果索引无效或者容量不足，直接返回当前价值0
        if (index < 0 || capacity <= 0)
            return 0;

        //不放第index个物品所得价值
        int res = solveKS(w, v, index - 1, capacity);
        //放第index个物品所得价值（前提是：第index个物品可以放得下）
        if (w[index] <= capacity) {
            res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
        }
        return res;
    }

    public static int knapSack(int[] w, int[] v, int C) {
        int size = w.length;
        return solveKS(w, v, size - 1, C);
    }

    public static void main(String[] args){
        int[] w = {2,1,3,2};
        int[] v = {12,10,20,15};
        System.out.println(knapSack(w,v,5));
    }
}

